#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n, V, v[N], w[N];
// int dp[N][N];
int dp[N];

int main()
{
// 二维版
    // cin >> n >> V;
    // for(int i = 1; i <= n; i++)
    //     cin >> v[i] >> w[i];
    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 1; j <= V; j++)
    //     {
    //         dp[i][j] = dp[i-1][j];
    //         if(j >= v[i]) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
    //     }
    // }
    // cout << dp[n][V] << endl;

    // memset(dp, 0, sizeof(dp));
    // for(int j = 1; j <= n; j++)
    //     dp[0][j] = -1;
    // for(int i = 1; i <= n; i++)
    // {
    //     for(int j = 1; j <= V; j++)
    //     {
    //         dp[i][j] = dp[i-1][j];
    //         if(j >= v[i] && dp[i-1][j-v[i]] != -1) dp[i][j] = max(dp[i][j], dp[i-1][j-v[i]] + w[i]);
    //     }
    // }
    // cout << (dp[n][V] == -1 ? 0 : dp[n][V]);

// 优化成一维
    cin >> n >> V;
    for(int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    for(int i = 1; i <= n; i++)
    {
        for(int j = V; j >= v[i]; j--)
        {
            dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;

    memset(dp, 0, sizeof(dp));
    for(int j = 1; j <= V; j++)
        dp[j] = -1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = V; j >= v[i]; j--)
        {
            if(dp[j-v[i]] != -1) dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
        }
    }
    cout << (dp[V] == -1? 0: dp[V]) << endl;

    return 0;
}
